package H_03difficult.h_2_t_76_最小覆盖子串;


class Solution {
    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] arr = new int['z' - 'A' + 1];
        for (char c : t.toCharArray()) {
            arr[c - 'A']++;
        }
        int cnt = t.length();
        int begin = -1;
        int count = s.length() + 1;
        char[] chars = s.toCharArray();
        int l = 0;
        int r = 0;
        while (r < s.length()) {
            if (arr[chars[r++] - 'A']-- > 0) {
                cnt--;
            }
            if (cnt == 0) {
                while (arr[chars[l] - 'A']++ < 0) {
                    l++;
                }
                if (count > r - l) {
                    begin = l;
                    count = r - l;
                }
                l++;
                cnt++;
            }
        }
        return begin == -1 ? "" : new String(chars, begin, count);
    }

    public static void main(String[] args) {
        minWindow("EBACDB","ABC");
    }
}